package com.acwing.partition1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class AC7混合背包问题 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int n = Integer.parseInt(s[0]), v = Integer.parseInt(s[1]);
        int[][] nums = new int[n][3];
        for (int i = 0; i < n; i++) {
            s = reader.readLine().split("\\s+");
            nums[i][0] = Integer.parseInt(s[0]);
            nums[i][1] = Integer.parseInt(s[1]);
            nums[i][2] = Integer.parseInt(s[2]);
        }
        writer.write(String.valueOf(dynamicProgramming(nums, v)));
        writer.flush();
    }

    private static int dynamicProgramming(int[][] nums, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int[] num : nums) {
            int v = num[0], w = num[1], s = num[2];
            if (s == 0) {
                //完全背包
                for (int j = v; j <= capacity; j++) {
                    dp[j] = Math.max(dp[j], dp[j - v] + w);
                }
            } else {
                //01背包是特殊的多重背包
                if (s == -1) s = 1;
                for (int k = 1; k <= s; k *= 2) {
                    for (int j = capacity; j >= k * v; j--) {
                        dp[j] = Math.max(dp[j], dp[j - k * v] + k * w);
                    }
                    s -= k;
                }
                for (int j = capacity; s != 0 && j >= s * v; j--) dp[j] = Math.max(dp[j], dp[j - s * v] + s * w);
                s = 0;
            }
        }
        return dp[capacity];
    }
}
